package Offer028;

import java.util.ArrayList;
import java.util.List;

/**
 * 展平多级双向链表
 * @author 23737
 * @time 2021.12.18
 */
public class Test {
    public static void main(String[] args) {

    }
}

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}

/**
 * dfs解题
 */
class Solution {
    List<Node> list = new ArrayList<>();
    public Node flatten(Node head) {
        if(head == null) return null;
        dfs(head);
        for(int i = 0; i < list.size() - 1; i++){
            Node pre = list.get(i);
            Node cur = list.get(i + 1);
            cur.prev = pre;
            pre.next = cur;
            pre.child = null;
        }
        return head;
    }

    //dfs解题
    public void dfs(Node root){
        if(root == null) return;
        list.add(root);
        dfs(root.child);
        dfs(root.next);
    }
}